#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<int> > combinationSum2(vector<int> &num, int target);

int main(){
    vector<int> num;
    num.push_back(0);
    combinationSum2(num, 1);
    return 0;
}

vector<vector<int> > combinationSum2(vector<int> &num, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    set<vector<int> > *pComb = new set<vector<int> >[target+1];
    vector<int> empty;
    pComb[0].insert(empty);
    for(vector<int>::iterator it = num.begin();
        it != num.end();
        ++it){
        // it is each num
        for(int i = target - *it;
            i >= 0;
            --i){
            // i is each possible slot
            if(pComb[i].size() > 0){
                for(set<vector<int> >::iterator iit = pComb[i].begin();
                    iit != pComb[i].end();
                    ++iit){
                    // iit is each existed vector of i
                    vector<int> tmp = *iit;
                    tmp.push_back(*it);
                    sort(tmp.begin(), tmp.end());
                    pComb[i+*it].insert(tmp);
                }
            }
        }
    }
    // get result
    vector<vector<int> > res;
    for(set<vector<int> >::iterator it = pComb[target].begin();
        it != pComb[target].end();
        ++it){
        res.push_back(*it);
    }
    delete []pComb;

    return res;
}

